package com.code.leetcode.idea;

/**
 * https://blog.csdn.net/sjp11/article/details/124366179
 *
 * TODO 添加动态规划
 */
public class LeetCodeIdea005_03 {
    public static void main(String[] args) {
        LeetCodeIdea005_03 leetCodeIdea005_03 = new LeetCodeIdea005_03();
        String test = "babad";
        String result = leetCodeIdea005_03.longestPalindrome(test);
        System.out.println(result);
    }

    public String longestPalindrome(String s) {
       int maxLen = 1;
       int maxStart = 0;
       int maxEnd = 0;
       int strLen = s.length();
       boolean[][] result = new boolean[strLen][strLen];
       for (int r = 1; r < strLen; r++) {
           for (int l = 0; l < strLen; l++) {
               if (s.charAt(l) == s.charAt(r) && (r - l <=2 || result[l+1][r-1])) {
                   result[l][r] = true;
                   if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                   }
               }

           }
       }
       return s.substring(maxStart, maxEnd + 1);
    }

}
